package main.java.indi.zyj.c150.back;

public class _11_NumIslands {

    public int numIslands(char[][] grid) {

        int res = 0;
        int i = grid.length;
        int j = grid[0].length;

        for (int k = 0; k < i; k++) {
            for (int l = 0; l < j; l++) {
                if (grid[k][l] == '1'){
                    res++;
                    dfs(grid, k, l);
                }
            }
        }

        return res;
    }

    // 从 (i, j) 开始，将与之相邻的陆地都变成海水
    void dfs(char[][] grid, int i, int j) {

        int m = grid.length, n = grid[0].length;
        if (i < 0 || j < 0 || i >= m || j >= n) {
            // 超出索引边界
            return;
        }
        if (grid[i][j] == '0') {
            // 已经是海水了
            return;
        }
        // 将 (i, j) 变成海水
        grid[i][j] = '0';
        // 淹没上下左右的陆地
        dfs(grid, i + 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);

    }


}
